package LeetCode.leetcode;

import java.util.Arrays;

/**
 * 下一个排列
 * 1-2-3   1-3-2
 * 1-3-2   2-1-3
 * 3-2-1   1-2-3
 * @author: leiwenkang02@meituan.com
 * @date: 2018/10/24
 * @time: 19:58
 */
public class Test31下一个排列 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 2};
        nextPermutation(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }


    public static void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) {
             return;
        }
        int index = nums.length - 1;
        while (index > 0) {//找到第一个前一位比后一位小的位置
            if (nums[index - 1] < nums[index]) {
                break;
            }
            index--;
        }
        if (index == 0) {//说明原数组本来就是倒序排列，是最大排列了
            //返回最小排列
            Arrays.sort(nums);
        } else {
            for (int i = nums.length - 1; i >= index ; i--) {
                if (nums[i] > nums[index - 1]) {
                    int temp = nums[i];
                    nums[i] = nums[index - 1];
                    nums[index - 1] = temp;
                    break;
                }
            }
            Arrays.sort(nums, index, nums.length);
        }
    }

}
